import heapq
from collections import defaultdict


def hash_status(status):
    """将状态转换为可哈希的元组（一维数组）"""
    return tuple(status)


def is_goal(status, goal):
    """检查当前状态是否为目标状态"""
    return status == goal


def manhattan_distance(status, goal_pos):
    """计算曼哈顿距离启发式函数"""
    distance = 0
    for i in range(9):
        if status[i] != 0:
            x_current, y_current = i // 3, i % 3
            x_goal, y_goal = goal_pos[status[i]]
            distance += abs(x_current - x_goal) + abs(y_current - y_goal)
    return distance


def solve_8_puzzle(initial_status):
    """使用 A* 算法求解 8-puzzle，返回被点击的数字序列"""
    # 目标状态：[1, 2, 3, 4, 5, 6, 7, 8, 0]
    goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
    goal_pos = {0: (2, 2)}  # 0 的目标位置是 (2, 2)
    for i in range(8):
        goal_pos[i + 1] = (i // 3, i % 3)  # 1~8 的目标位置

    # 检查是否有解（逆序数同奇偶性）
    flat_initial = [num for row in initial_status for num in row]
    inversions = 0
    for i in range(9):
        for j in range(i + 1, 9):
            if flat_initial[i] != 0 and flat_initial[j] != 0 and flat_initial[i] > flat_initial[j]:
                inversions += 1
    if inversions % 2 != 0:
        return -1  # 无解

    # 初始化
    initial_flat = [num for row in initial_status for num in row]
    open_list = []
    heapq.heappush(open_list, (0 + manhattan_distance(initial_flat, goal_pos), 0, initial_flat, []))
    min_distance = defaultdict(lambda: float('inf'))
    min_distance[hash_status(initial_flat)] = 0

    while open_list:
        _, g, current_status, path = heapq.heappop(open_list)
        if is_goal(current_status, goal):
            return path

        if min_distance[hash_status(current_status)] < g:
            continue

        zero_pos = current_status.index(0)
        x, y = zero_pos // 3, zero_pos % 3

        # 四个可能的移动方向
        moves = [
            (-1, 0),  # 上
            (1, 0),  # 下
            (0, -1),  # 左
            (0, 1)  # 右
        ]

        for dx, dy in moves:
            new_x, new_y = x + dx, y + dy
            if 0 <= new_x < 3 and 0 <= new_y < 3:
                new_pos = new_x * 3 + new_y
                new_status = current_status.copy()
                new_status[zero_pos], new_status[new_pos] = new_status[new_pos], new_status[zero_pos]
                moved_num = current_status[new_pos]  # 被点击的数字
                new_g = g + 1
                new_h = manhattan_distance(new_status, goal_pos)
                if min_distance[hash_status(new_status)] > new_g:
                    min_distance[hash_status(new_status)] = new_g
                    heapq.heappush(open_list, (new_g + new_h, new_g, new_status, path + [moved_num]))

    return -1  # 无解


if __name__ == '__main__':
    initial_status = [
        [4, 7, 5],
        [3, 1, 2],
        [8, 6, 0]
    ]
    solution = solve_8_puzzle(initial_status)
    if solution == -1:
        print("无解")
    else:
        print("请按顺序点击以下数字：")
        print(f"最少需要 {len(solution)} 步，顺序为：{' → '.join(map(str, solution))}")
